package org.example.BinaryTree;

import java.util.*;

public class Maximum_binary_tree {
    public static void main(String[] args) {
        //最大二叉树

        //给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
        //创建一个根节点，其值为 nums 中的最大值。
        //递归地在最大值 左边 的 子数组前缀上 构建左子树。
        //递归地在最大值 右边 的 子数组后缀上 构建右子树。
        //返回 nums 构建的 最大二叉树 。
        int[] nums = {1,2,3};
        search(constructMaximumBinaryTree(nums));
    }

    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) return null;
        return getNode(nums, 0, nums.length - 1);
    }

    public static TreeNode getNode(int[] nums, int begin, int end) {
        if (begin > end) return null;
        List<Integer> list = getMax(nums, begin, end);
        TreeNode node = new TreeNode(list.get(0));
        node.left = getNode(nums,begin, list.get(1)-1);
        node.right = getNode(nums,list.get(1)+1,end);
        return node;
    }

    //获取最大值
    public static List<Integer> getMax(int[] nums, int begin, int end) {
        ArrayList<Integer> arr = new ArrayList<>();
        int max = nums[begin];
        arr.add(max);
        arr.add(begin);
        for (int i = begin; i <= end; i++) {
            if (max < nums[i]) {
                max = nums[i];
                arr.set(0,max);
                arr.set(1,i);
            }
        }
        return arr;
    }
    //遍历
    public static void search(TreeNode root){
        if (root==null) return;
        System.out.print(root.val+" ");
        search(root.left);
        search(root.right);
    }
}
